package done.easy_001_100;

import lombok.extern.slf4j.Slf4j;
import org.junit.Test;

import static com.study.util.LogUtil.info;
import static java.lang.Math.max;

/**
 * 53. Maximum Subarray
 * <p>
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * <p>
 * 示例:
 * 输入: [-2, 1, -3, 4, -1, 2, 1, -5, 4],
 * 输出: 6
 * 解释: 连续子数组 [4, -1, 2, 1] 的和最大，为 6。
 * <p>
 * 这道题让我们求最大子数组之和，并且要我们用两种方法来解，分别是O(n)的解法，
 * 还有用分治法Divide and Conquer Approach，这个解法的时间复杂度是O(nlgn)，
 * 那我们就先来看O(n)的解法，定义两个变量res和curSum，其中res保存最终要返回的结果，
 * 即最大的子数组之和，curSum初始值为0，每遍历一个数字num，比较curSum + num和
 * num中的较大值存入curSum，然后再把res和curSum中的较大值存入res，以此类推直到
 * 遍历完整个数组，可得到最大子数组的值存在res中.
 *
 * @author 大硕
 * 2019-03-23 10:03 AM
 **/
@Slf4j
public class MaximumSubarray {

    @SuppressWarnings("all")
    public int maxSubArray(int[] nums) {
        // 190323 first
        // 190416 second 用了两次解决的，思路还是没想出来
        // 190527 third 看了答案做出来的 这个题被快手考过，必需要会
        // 190528 fourth 居然又忘了... 看了答案做出来的
        // 190601 fifth 一遍过
        // 190617 sixth 看答案做出来的，全忘了......
        return -1;
    }

    @Test
    public void test() {
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        info("6 -> {}", maxSubArray(nums));
    }
}




























/*
public int maxSubArray(int[] nums) {
    //MIN_VALUE 最小负数
    int res = MIN_VALUE;
    int sum = 0;
    for (int num : nums) {

        // 加num还不如不加num的话
        // 前面就都不要了
        // 之前的累加和是 -1 如果 -1 + -1 = -2   max(-2, -1) == -1
        sum = max(sum + num, num);

        res = max(res, sum);
    }
    return res;
}
*/
